package com.liezh.structurealgorithm;

import java.util.Arrays;

/**
 * 快排
 * @author liezh
 * @date 2020-10-10
 */
public class QuickSort {


    public static void main(String[] args) {
        int[] array = {-1, 9, 10, 2, 4, 23, 8, 5, 47, 4, 1, 0, -10};
        customQuickSort(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 之定义快排
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static void customQuickSort(int[] array, int low, int high) {
        if (array.length <= 1) {
            return;
        }
        if (low >= high) {
            return;
        }
        int key, i, j;
        key = array[low];
        i = low;
        j = high;
        while (i < j) {
            // 从高位往低位找，往左，找到第一个小于标记值key，并记录位置j
            while (array[j] >= key && i < j) {
                j--;
            }
            // 从低位往高位找，往右，找到第一个大于标记值key，并记录位置i
            while (array[i] <= key && i < j) {
                i++;
            }
            // 交换数字
            int temp = array[j];
            array[j] = array[i];
            array[i] = temp;
        }
        // 把key的位置移到 i 上，作为中位
        array[low] = array[i];
        array[i] = key;

        // 左边切分递归
        customQuickSort(array, low, i - 1);
        // 右边切分递归
        customQuickSort(array, i + 1, high);
    }


}
